<!DOCTYPE html>
<html lang="zh-CN">

<head>
    <meta charset="utf-8">
    <meta name="viewport" content="width=device-width, initial-scale=1, shrink-to-fit=no">
    <link rel="shortcut icon" href="">
    <title>递归分割</title>
    <style type="text/css">
        body {
            background-color: #eccc68;
        }

        canvas {
            width: 400px;
            height: 300px;
            border: 1px solid black;
        }
    </style>
</head>

<body>
    <h1>递归分割</h1>
    <script type="module">
        // import * as TWO from './two.js'
        import { Scene, Render, Rect, PickContrls, Vector2 } from './two/two.js'
        // import Point from './two.js'
        // import Render from './two.js'
        const LOG = 0
        const width = 400, height = 300, edge = 20
        let cols = ~~((width * 2) / edge) - 1, rows = ~~((height * 2) / edge) - 1

        let render = new Render()
        render.setSize(width, height)
        render.setPixelRatio(2)
        render.setTickLength(1000 / 10)
        render.setAnimationLoop(animation)
        document.querySelector('body').appendChild(render.domElement)

        const scene = new Scene()
        const colorMap = {
            0: 'hsl(220, 20%, 50%)', // 路
            1: 'hsl(120, 100%, 50%)', // 墙
            2: 'hsl(0, 100%, 50%)',  // 待选
        }
        // scene.add(rect)
        // 0-路, 1-墙, 2-待选
        let map = new Array()
        for (let x = 0; x < cols; ++x) {
            map[x] = new Array()
            for (let y = 0; y < rows; ++y) {
                map[x][y] = 0
                const rect = new Rect(edge - 3, edge - 3)
                rect.setAttribute('stroke', false)
                rect.position.copy({ x: (x + 1) * edge, y: (y + 1) * edge })
                scene.add(rect)
            }
        }
        for (let x = 0; x < cols; ++x) {
            map[x][0] = 1
            map[x][rows - 1] = 1
        }
        for (let y = 0; y < rows; ++y) {
            map[0][y] = 1
            map[cols -1][y] = 1
        }

        /*
        const controls = new PickContrls(scene, render.domElement)
        controls.setPixelRatio(2)
        */
        let x_b = ~~(Math.random() * (cols - 1)) + 1, y_b = ~~(Math.random() * (rows - 1)) + 1
        // map[x_b][y_b] = 0
        let openlist = []
        clip(1, 1, cols - 2, rows - 2)
        function animation() {
            render.render(scene)
            if (openlist.length > 0) {
                let target = openlist[openlist.length - 1]
                LOG && console.log(JSON.stringify(target))
                for (let i = target.x1; i <= target.x2; ++i) map[i][target.ry] = 1
                for (let i = target.y1; i <= target.y2; ++i) map[target.rx][i] = 1
                for (let i = 0; i < target.holds.length; ++i) {
                    map[target.holds[i].x][target.holds[i].y] = 0
                }
                openlist.splice(openlist.length - 1, 1)
            }
            display()
        }
        function clip(x1, y1, x2, y2) {
            if (x2 - x1 < 2 || y2 - y1 < 2) return
            let x = x1 + 1
            let y = y1 + 1
            if (x2 - x1 >= 3) {
                x = x1 + 1 + ~~(Math.random() * (x2 - x1 - 2))
            }
            if (y2 - y1 >= 3) {
                y = y1 + 1 + ~~(Math.random() * (y2 - y1 - 2))
            }
            x = ~~(x / 2) * 2
            y = ~~(y / 2) * 2
            LOG && console.log('-->' + x1 + ", " + y1 + " | " + x2 + ", " + y2 + " | " + x + ", " + y)
            /*
            for (let i = x1; i <= x2; ++i) map[i][y] = 1
            for (let i = y1; i <= y2; ++i) map[x][i] = 1

            */
            clip(x1, y1, x - 1, y - 1)
            clip(x + 1, y1, x2, y - 1)
            clip(x1, y + 1, x - 1, y2)
            clip(x + 1, y + 1, x2, y2)

            /*

            */
            let holds = []
            let r = [0, 0, 0, 0]
            r[~~(Math.random() * 3) ] = 1
            for (let i = 0; i < 4; ++i) {
                if (r[i] === 0) {
                    let rx = x, ry = y
                    switch(i) {
                        case 0:
                            do {
                                rx = x1 + ~~(Math.random() * (x - x1))
                            } while(map[rx-1][ry] + map[rx+1][ry] + map[rx][ry-1] + map[rx][ry+1] > 2)
                            break
                        case 1:
                            do {
                                ry = y1 + ~~(Math.random() * (y - y1))
                            } while(map[rx-1][ry] + map[rx+1][ry] + map[rx][ry-1] + map[rx][ry+1] > 2)
                            break
                        case 2:
                            do {
                                rx = x + 1 + ~~(Math.random() * (x2 - x))
                            } while(map[rx-1][ry] + map[rx+1][ry] + map[rx][ry-1] + map[rx][ry+1] > 2)
                            break
                        case 3:
                            do {
                                ry = y + 1 + ~~(Math.random() * (y2 - y))
                            } while(map[rx-1][ry] + map[rx+1][ry] + map[rx][ry-1] + map[rx][ry+1] > 2)
                            break
                    }
                    // map[rx][ry] = 0
                    holds.push({x: rx, y: ry})
                }
            }
            let target = {x1: x1, y1: y1, x2: x2, y2: y2, rx: x, ry: y, holds: holds}
            openlist.push(target)
        }
        function display() {
            let index = 0
            for (let x = 0; x < cols; ++x) {
                for (let y = 0; y < rows; ++y) {
                    const rect = scene.children[index++]
                    rect.setAttribute('fillStyle', colorMap[map[x][y]])
                }
            }
        }

    </script>

    <code style="width: 800px; height: 250px">
        <p>递归切割算法</p>
        <p>首先假设迷宫全是路，在里面画四面墙，把迷宫分割成四个新区域</p>
        <p>随机选择三面墙打通，这时原本隔开的四个区域又被打通了</p>
        <p>以此类推，在四个新区域内继续设墙分割区域，然后把墙打通，直到不能继续分割才结束</p>
        <a href="https://blog.csdn.net/jjwwwww/article/details/82901326">随机迷宫生成算法——递归分割算法</a>
    </code>
</body>

</html>